# encoding: utf-8
""" 
@version: v1.0 
@author: autumner 
@license: Apache Licence  
@contact: 18322313385@163.com 
@site:  https://gitee.com/autumner/pythoncookbook.git
@software: PyCharm 
@file: selection_sort.py 
@time: 2019/7/1 9:52
"""
'''
选择排序不受输入数据的影响，即在任何情况下时间复杂度不变。选择排序每次选出最小的元素，因此需要遍历 n-1 次。
'''
def selectionSort(nums):
    for i in range(len(nums) - 1):
        # 遍历len(nums) - 1次
        minIndex = i
        for j in range(i + 1, len(nums)):
            if nums[j] < nums[minIndex]:
                # 更新最小值索引
                minIndex = j
        nums[i], nums[minIndex] = nums[minIndex], nums[i]
    return nums

# Example use
nums = [3, 2, 15, 26, 27,36, 38, 47, 2, 19, 48, 50, 44, 4]
print(selectionSort(nums))